前言

二元樹真的是演算法裡非常大的一個章節。(看看 Leetcode，有 Binary Tree 的 Tag 的題目就有 100多題)
因為樹這個結構本身就是透過指標來鏈結不同的物件，廣義來說，多數高級結構，都可以由這個方式推導過來，如圖，圖就是有環的鏈結結構(樹無環，某種意義上可說是有環的樹)，鏈結串列也可以看成是單子樹的樹狀，要說的是，樹的結構真的很重要，有時候其他鏈結結構的題目，也會用到來自樹的走訪觀念解題。

在有了昨天基本的前序、中序、後序的概念後，今天再多看一點，關於樹的結構的操作與這三種方式如何幫助我們遍歷樹。寫樹相關的題目，最好是能對自己用的走訪方式有概念，到底現在寫的寫法是前、中、後的哪一種？為什麼要用這種走訪方式，是不是能夠用其他走訪方式來達成同樣效果。

如果能對同一題做到多種解題思路的考察，而不是看 Submit 通過了就過了，練起來的效果會更加紮實。

走訪的特性

一般來說，我們無意識寫出來的、在題目順序不敏感(前序中序後序皆可的情況下)，我們容易寫出前序，但在走訪順序上，相較另外兩者，他並沒有太特別的優點。
中序在二元搜尋樹(Binary Search Tree，BST)中，能夠正好得出由小到大的結果，凡是有序的樹的遍歷，想想中序是不是剛好符合結構的遞增遞減定義。
後序的順序是左右子樹走完，才回來中間，帶來的好處是當回到中間節點的時候，我們已經搜齊了左右子樹的訊息，如果題目是需要左右子樹的資訊才能夠處理，後序很可能會是優先選項。

Convert Sorted Array to Binary Search Tree

題目給了一個有序陣列，讓我們把陣列轉為二元搜尋樹。在二元樹的題目裡面，常常會看到敘述上用陣列來表達樹的結構，一般是用完全二元樹的方式來表達，缺的點會用 null 補上表示。
例如 [1,2,3,Null,5,6] 代表的就是這樣一棵樹：

     1
   /   \
  2     3
 / \   /
N  5  6

把 null 看進去，是不是就是一棵完全二元樹了呢。
二元搜尋樹就是指，在整棵樹的結構裡，維持著左子樹所有的節點都小於父節點，右子樹所有的節點都大於父節點，這樣的樹，就像為搜尋建立了索引，在這樣的結構裡，查找是否存在特定值所需的時間複雜度為 O(log n)，小於一般線性搜索的 O(n)。
透過這題，我們來看一下怎麼用陣列構造一個二元搜尋樹。

一樣先列出流程，因為是有序陣列，我們保證最左為最小，最右為最大。
構造上我們可以知道中間為中間的值，而左邊整棵子樹必定小於中間，右邊整棵子樹必定大於中間，透過這個認識，當我們訂出中間以後，就能知道剩下那些元素會分別用於左右子樹。
所以我們透過 index 找出正中間 index 的數字，把它當作中間點，左子樹的構造則是由第一個到中間點之前的元素來做，右子樹的構造則是由中間點之後到最後一個的元素來做。
以此遞迴，一旦左子樹預期的 index > 右子樹預期的 index，表示已經到底了，再提供的區間內，找不到比當前節點更小的數了，終止遞迴。
透過上面的邏輯，我們可以寫出下面的遞迴：

public class Solution {
    public TreeNode SortedArrayToBST(int[] nums) {
        var left = 0;
        var right = nums.Length - 1;
        return ConstructBST(nums, left, right);
    }

    private TreeNode ConstructBST(int[] nums, int left, int right){
        if(left > right){
            return null;
        }
        var mid = (left + right)/2;
        var node = new TreeNode(nums[mid]);
        node.left = ConstructBST(nums, left, mid - 1);
        node.right = ConstructBST(nums, mid + 1, right);
        return node;
    }
}

透過這樣如此一來，我們就能構造出一棵二元搜尋樹，也提前預習一下二元搜尋樹的定義與架構，關於二元搜尋樹的插入與移除，我們會有另一篇單獨來討論。

Invert Binary Tree

給你一個根結點，翻轉左右子樹後回傳翻轉後的根結點。
想一下，如果要去構造這個翻轉的寫法，什麼序的遍歷會是最合適的？
實際操作流程是，找到每個中間節點，翻轉左右節點，再往下去找左右節點，把左右節點視為中間節點，翻轉再下一層的左右節點。
聽起來是不是完全就是後序的走訪順序？沒錯，其實這題看上去叫做翻轉二元樹，實際上就是後序走訪然後交換左右子傑點，程式碼如下。

public class Solution {
    public TreeNode InvertTree(TreeNode root) {
        Traverse(root);
        return root;
    }
    private TreeNode Traverse(TreeNode node){
        if(node == null){
            return null;
        }
        (node.left, node.right) = (node.right, node.left);
        Traverse(node.left);
        Traverse(node.right);
        return node;
    }
}

就像這樣遍歷一遍，整顆二元樹就被翻轉了。
符合我們上面對後序的註解：需要蒐齊左右子樹資訊後，再回到中間節點 ─ 記得，這就是後序。

Populating Next Right Pointers in Each Node

這題是一個讓我們調整樹的構造，本來節點只有左右子節點，現在多一個叫做 next 的子節點，這個子節點指向同層的右方子節點，構造完成後，回傳根結點。

想一下在這題，我們應該怎麼操作？
如果用從上至下的訪問順序，流程上應該是必須要從父節點才能讓左子節點指向右子節點(因為在父層的角度才知道誰是誰的右節點)。所以流程應該是當訪問到的節點為空，則返回空(無須操作)。
如果左子節點不為空，則我們把左子節點指向右子節點，不用特別判斷右子節點為不為空，即使為空也是剛好指向 null 而已。
此時右子節點該如何判斷要不要指向另一顆子樹的左子節點呢？這就是這題精妙的地方，通過檢查父節點本身的 next 有沒有下一顆同級樹，有的情況下才需要指向該樹(父節點的 next)的左子樹。
接著再從左接到右，直至整棵樹接完。

public class Solution {
    public Node Connect(Node root) {
        if(root == null) return null;
        if(root.left != null)
        {
            root.left.next = root.right;
            if(root.next != null){
                root.right.next = root.next.left;
            }
        }
        Connect(root.left);
        Connect(root.right);
        return root;
    }
}

可以看到這邊因為是個可遞迴的重複概念，最後我們是用遞迴來實現，且終止條件就是該點為不為空，寫在最開頭，如此我們在往下一層走的時候也不用先判斷該子節點為不為空，就讓他進去函式，直接在開頭判斷就好。
那這題是走訪順序的哪一種呢？走訪處理順序本身是前序，因為是中左右的處理順序，不過實際上處理比較像是層級遍歷，我們在父節點的時候就已經把左到右的指向處理完畢 ─ 明天，讓我們來看一下如果要從上到下走訪樹層級的話，層級遍歷該怎麼處理。